package puzzle.projecteuler.p100;

public class Problem076C {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		long s = System.currentTimeMillis();
		System.out.println(p(5));
		System.out.println(p(6));
		System.out.println(p(7));
		System.out.println(p(8));
		System.out.println(p(9));
		System.out.println(p(10));
		System.out.println((System.currentTimeMillis()-s) + " ms");
	}
	
	/**
	 * the number of ways to write n as sum of m numbers is p(n,m).
	 * p(n,m) = p(n-1, m-1) + p(n-m, m)
	 * p(n,m) = 0, if n < m
	 * p(n,m) = 1, if n = m
	 * @param n
	 * @param m
	 * @return
	 */
	public static int p(int n, int m) {
		if (n <= 0 || m <= 0) {
			return 0;
		} else if (n < m) {
			return 0;
		} else if (n == m) {
			return 1;
		} else {
			return p(n-1, m-1) + p(n-m, m);
		}
	}
	
	public static int p(int n) {
		int p = 0;
		for (int i = 2; i <= n; i ++) {
			p += p(n,i);
		}
		return p;
	}
}
